#include "albero.h"

#if ALBERO_KERNEL_MODE
#include <linux/kernel.h> //for printk
#include <linux/string.h> //for strcpy, strlen
#include <linux/slab.h>   //for kmalloc

#define albero_malloc(size)      kmalloc(size, GFP_KERNEL)
#define albero_free(t) kfree(t);
#else
#include <stdio.h>  //for printf
#include <stdlib.h> //for malloc, free
#include <string.h> //for strcpy, etc...
#define albero_malloc(size) malloc(size)
#define albero_free(t) free(t)
#endif

#undef albero_debug             /* undef it, just in case */
#ifdef ALBERO_DEBUG
#  ifdef ALBERO_KERNEL_MODE
     /* This one if debugging is on, and kernel space */
#    define albero_debug(fmt, args...) printk( KERN_DEBUG "albero: " fmt, ## args)
#  else
     /* This one for user space */
#    define albero_debug(fmt, args...) fprintf(stderr, fmt, ## args)
#  endif
#else
#  define albero_debug(fmt, args...) /* not debugging: nothing */
#endif

#  ifdef ALBERO_KERNEL_MODE
#    define albero_print(fmt, args...) printk( KERN_DEBUG "albero: " fmt, ## args)
#  else
     /* This one for user space */
#    define albero_print(fmt, args...) fprintf(stderr, fmt, ## args)
#  endif


/*
********************************************************************************
*************************** VISITA DELL' ALBERO ********************************
********************************************************************************
*/

/*
  Visita l'albero in preordine:
  stampa prima la radice, poi scende a sinistra e poi a destra.
  In questo modo si ottiene una rappresentazione top-down dell'albero.
*/
int preorder (tree * t, char * buffer, unsigned long *lim, unsigned long *start){
    int dup = 0;
  albero_debug("preorder buf:%p, lim:%lu, start:%lu", buffer, *lim, *start); //stampa di debug
  *start=writeString(t->string, buffer, *start, *lim);//scrittura su file e salvataggio della prima posizione libera
  if (t->ric > 1) {
      dup = (strlen(t->string)+1) * (t->ric-1);
      //printf("preorder: dup %d ric %d s %s\n", dup, t->ric-1, t->string);
  }
  if (t->left != NULL ) dup += preorder(t->left, buffer, lim, start);
  if (t->right != NULL ) dup += preorder(t->right, buffer, lim, start);
  return dup;
}

/*
  Visita l'albero in ordine:
  stampa prima il nodo più a sinistra, poi suo padre e poi suo fratello (a destra)
  risale e stampa il padre del sottoalbero destro e scende nel sottoalbero sinistro.
  Il risultato è la stampa in ordine alfabetico delle parole.
*/
void inorder (tree * t, char * buffer, unsigned long *lim, unsigned long *start){
  if (t->left != NULL ) inorder(t->left, buffer, lim, start);
  albero_debug("preorder buf:%p, lim:%lu, start:%lu", buffer, *lim, *start); //stampa di debug
  *start=writeString(t->string, buffer, *start, *lim);//scrittura su file e salvataggio della prima posizione libera
  if (t->right != NULL ) inorder(t->right, buffer, lim, start);
}

/*
  Visita l'albero in postordine:
  Stampa l'albero partendo dal nodo più in basso a sinistra, poi suo fratello a destra, poi
  il padre, e risale fino alla radice dell'albero.
  Restituisce una rappresentazione dalle foglie alla radice dell'albero.
*/
void postorder (tree * t, char * buffer, unsigned long *lim, unsigned long *start){
  if (t->left != NULL ) postorder(t->left, buffer, lim, start);
  if (t->right != NULL )postorder(t->right, buffer, lim, start);
  albero_debug("preorder buf:%p, lim:%lu, start:%lu", buffer, *lim, *start); //stampa di debug
  *start=writeString(t->string, buffer, *start, *lim);//scrittura su file e salvataggio della prima posizione libera
}

/*
  Visita l'albero in modo inverso della inorder:
  esegue una visita invertita rispetto ad inorder, prima il nodo più profondo a destra, poi risale fino alla radice 
  per ridiscendere fino al nodo più profondo a sinistra.
  Si ottiene una lista in ordine alfabetico inverso delle parole inserite.
*/
void invorder (tree * t, char * buffer, unsigned long *lim, unsigned long *start){
  if (t->right != NULL) invorder(t->right, buffer, lim, start);
  albero_debug("preorder buf:%p, lim:%lu, start:%lu", buffer, *lim, *start); //stampa di debug
  *start=writeString(t->string, buffer, *start, *lim);//scrittura su file e salvataggio della prima posizione libera
  if(t->left != NULL) invorder(t->left, buffer, lim, start);
}



/*
********************************************************************************
**************** BONUS PER IL CONTEGGIO DELLE PAROLE PIÙ INSERITE **************
****************************** E CONTEGGIO DEI VERBI ***************************
********************************************************************************
*/

/*
  Controlla se una parola è un verbo all'infinito (*are, *ere, *ire):
  comtrolla che le ultime due lettere siano 'e' e 'r' e  che l'ultima sia
  'a' o 'e' o 'i'.
  Restituisce un intero con funzione di booleano (1 true, 0 false).
*/

int isVerb(char str[]){
  int l = strlen(str);
  if (str[l-1]=='e' && str[l-2]=='r' && (str[l-3]=='a' || str[l-3]=='e' || str[l-3]=='i')){
    return 1;
  }
  else return 0;
}


/*
  Questa funzione ricerca le prima k parole più inserite.
  Prende in input la radice dell'albero, un vettore di stringhe (vettore di vettori di
  caratteri), un vettore di interi, e il numero delle prime parole da trovare.
  Il vettore di stringhe e di interi devono essere dichiarati delle dimensioni corrette
  (k) all'esterno della funzione in modo da poter eseguire un "return" multiplo ed 
  inizializzati correttamente (a null).
  
  Il vettore vstr contiene le prime k ricorrenze dove in posizione 0 c'è la stringa
  che compare più volte, in 1 la seconda, in 2 la terza...
  Il vettore nstr contiene il numero di volte che compare ogni stringa.
*/

void moreWritedPlus(tree * t, char * vstr[], int nstr[], int k, int *nparole, int *nverbi){
  int l=k, i,j;//i e j per evitare di compilare in c99 mode

  *nparole = *nparole + t->ric;
  if (isVerb(t->string)) {
      *nverbi = *nverbi + t->ric;
  }

  for (i=0; i<l; i++){
    if (t->ric>nstr[i]){ //controlla se la stringa che ha selezionato nell'albero ricorre più volte di una delle stringhe già salvate
   
      for (j=(l-i-1); j>0; j--){ //se la parola ricorre più volte si "spostano" verso destra tutti i valori dei due vettori 
	nstr[i+j]=nstr[i+j-1];
	vstr[i+j]=vstr[i+j-1];
      }

      nstr[i]=t->ric;//e si inserisce la stringa trovata. l'ultimo valore del vettore viene perso.
      vstr[i]=t->string;
      i=l;
      /*
	Non viene eseguito nessun controllo sulla validità dell'intero vettore, 
	come se si richiedono le prime 4 parole e l'albero ne contiene solo 3.
	Questo controllo deve essere effettuato al momento della stampa.
       */
    }
  }

  //il controllo prosegue in ricorsione e sinistra e a destra.
  if(t->left != NULL) moreWritedPlus(t->left, vstr, nstr, k, nparole, nverbi);
  if(t->right != NULL) moreWritedPlus(t->right, vstr, nstr, k, nparole, nverbi);
}



/*
  Stampa le prime k parole:
  interfaccia per la funzione moreWrited, stampa nel buffer l'elenco delle k parole
  più usate.
*/

void printMoreDebug (tree * t, int k){
  int i;
  char ** vstr; 
  int * nstr;
  int nverbi, nparole;

  nverbi = 0;
  nparole = 0;

  vstr = albero_malloc(k*sizeof(char *));
  nstr = albero_malloc(k*sizeof(int));
  
  for (i=0; i<k; i++){
    vstr[i]=NULL;
    nstr[i]=0;
  }
  
  moreWritedPlus(t,vstr, nstr, k, &nparole, &nverbi);
  i=0;

  while(i < k && nstr[i] != 0){
    albero_print("bonus: %s %d\n", vstr[i], nstr[i]);
    i++;
  }
  albero_print("parole totali: %d, numero verbi infinito: %d\n", nparole, nverbi);
  
  albero_free(vstr);
  albero_free(nstr);
}


//========================== Gestione dell'albero ==============================

/*
********************************************************************************
********************* FUNZIONI DI GESTIONE DELL'ALBERO *************************
********************************************************************************
*/

/*
  Questa funzione serve a creare un nuovo nodo collegandlo ad un albero t e
  inserendoci un valore val presi in input, il numero di ricorrenze è 
  impostato a 1.
  I sottoalberi destro e sinistro sono null (cioè creo una foglia).
*/

tree* create(tree * t, char * val){
  tree * n = (tree *) albero_malloc(sizeof(tree)); //alloca con kmalloc se si esegue nel kernel o con malloc se si è furi dal kernel.
  n->string=val;
  n->ric=1;
  n->left=NULL;
  n->right=NULL;
  albero_debug("Inserito: %s \n",n->string); //stampa un output di debug con printk o printf a seconda.
  return n;
}


/*
  Inserisce un valore nell'albero: 
  compie una ricerca ricorsiva finchè:
  - trova il valore cercato, quindi incrementa la variabile ric del nodo
  - viene indirizzato ad una foglia vuota (puntatore null) e quindi crea un nuovo 
    nodo contente quel valore chiamando create.
*/

void insert (tree *t, char str[]){
  int cmp;

  cmp = strncmp(str, t->string, 256);
  if (cmp>0) cmp=1;
  if (cmp<0) cmp=2;
  
  switch (cmp){
  case 0 : //la parola è già presente, si incrementa
    albero_debug("inc ");
    t->ric++;
    break;

  case 1: //la parola è "maggiore" di quella nel nodo attuale, si va in ricorsione a destra
    albero_debug("right ");
    if (t->right == NULL) t->right=create(t, str);
    else insert(t->right, str);
    break;

  case 2: //la parola è "minore" di quella nel nodo attuale, si va in ricorsione a sinistra
    albero_debug("left ");
    if (t->left == NULL) t->left=create(t, str);
    else insert(t->left, str);
    break;

  default : //questo caso non dovrebbe mai essere raggiunto
    albero_debug("Error! Insert value in tree failed \n");

  }

}

//Usata nel test
int copy_words(char *src, char *dst, int lim, tree *tr, char **start_at, int end) {
    int q_pos = 0;
    int err = 0;
    char *c, *start;

    while (q_pos < lim) {
	albero_debug("q_pos: %d", q_pos);
	c = src+q_pos;
	if (isChar(*c)) {
	    start = dst+q_pos;
	    if (start == NULL) {
		return 2;
	    }
	    *start = *c;
	    albero_debug("start: %c", *start);
	    while (++q_pos < lim) {
		c = src+q_pos;
		if (isChar(*c)) {
		    albero_debug("c: %c", *c);
		    *(dst+q_pos) = *c;
		}
		else {
		    albero_debug("end %d", q_pos);
		    break;
		}
	    }
	    *(dst+q_pos) = '\0';
	    albero_debug("found: %s", start);
	    if (tr->string == NULL)
		tr->string = start;
	    else
		insert(tr, start);
	}
	else {
	    *(dst+q_pos) = '\0';
	}
	q_pos++;
    }
    return err;
}

/*
  ********************************************************************************
  **************** FUNZIONI PER UTILIZZARE LE STRUTTURE DATI**********************
  ************************ FORNITE DALLO SCULL DEVICE*****************************
  ********************************************************************************  
*/

/*
  Controlla se un carattere è alfanumerico, considera tutta la punteggiatura,
  la spaziatura e i caratteri speciali alla stessa maniera.
  La scelta è stata fatta per evitare di considerare la punteggiatura di un
  testo come parte della parola.
*/
int isChar(char c){
  return ((c>='a' && c<='z') || (c>='A' && c<='Z') || (c>='0' && c <='9'));
}

void tree_free(tree *t, int free_string) {
	if (t != NULL) {
		tree_free(t->left, free_string);
		tree_free(t->right, free_string);
		if (free_string)
		    albero_free(t->string);
		albero_free(t);
	}
	}

int writeString(char * str, char * buffer, unsigned long start, unsigned long size){
  int i=0;
 
  if (start < size) { 
  	while (isChar(str[i]) && start<size){
	    albero_debug("writeString: %c", str[i]);
	    buffer[start]=str[i];
	    start++;
	    i++;
	}
	if (start < size) {
		buffer[start]=' ';
		start++;
	}
  }
  return start;
}
